
/*
 * Question: Try to determine whether a binary is complete.
 */

#include <iostream>
#include <queue>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

void visit(bitree *rt)
{
    cout << rt->key << " ";
}

/*
 * Travel the binary tree in level order.
 * If a empty subtree is found and then an nonempty
 * subtree appears, the binary tree is not complete.
 * Otherwise, it is.
 */
bool iscomplete(bitree *rt)
{
    bool iscomp;
    bitree *p;
    queue<bitree *> q;

    q.push(rt);
    iscomp = false;
    while(!q.empty()){
        p = q.front(); q.pop();
        if(iscomp && p){
            iscomp = false;
            break;
        }
        else{
            if(!p) iscomp = true;
            else{
                q.push(p->lchild);
                q.push(p->rchild);
            }
        }
    }

    return iscomp;
}

int main()
{
    bitree *rt;

    bitree_create<bitree,char>(rt, "ex49.txt");
    cout << iscomplete(rt) << endl;

    return 0;
}
